/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/maximum-subarray-iii
@Language: C++
@Datetime: 16-02-09 09:02
*/

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @param k: An integer denote to find k non-overlapping subarrays
     * @return: An integer denote the sum of max k non-overlapping subarrays
     */
    int maxSubArray(vector<int> nums, int k) {
        // write your code here
        int n=nums.size();
		int MIN=-1<<30;
        vector<vector<int> > global(n+1,vector<int>(k+1,MIN));
        vector<vector<int> > local(n+1,vector<int>(k+1,MIN));
		for(int i=1;i<=k;++i)
			local[0][i]=0;
        for(int i=1;i<=n;++i){
            global[i][0]=local[i][0]=0;
            for(int j=1;j<=k &&j<=i;++j){
                local[i][j]=max(local[i-1][j]+nums[i-1],global[i-1][j-1]+nums[i-1]);
                global[i][j]=max(global[i-1][j],local[i][j]);
            }
        }
        return global[n][k];
    }
};
